package 算法.LeetCode91.每日打卡题目;

import java.util.*;

/**
 * @author:谢君臣
 * @Date:2021/3/1717:49
 * @version:1.0
 * @function: 在一个 N x N 的坐标方格 grid 中，每一个方格的值 grid[i][j] 表示在位置 (i,j) 的平台高度。
 * 现在开始下雨了。当时间为 t 时，此时雨水导致水池中任意位置的水位为 t 。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。
 * 你从坐标方格的左上平台 (0，0) 出发。最少耗时多久你才能到达坐标方格的右下平台 (N-1, N-1)？
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/swim-in-rising-water
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day34 {
    public static void main(String[] args) {
        System.out.println(swimInWater(new int[][]{{0, 1, 2, 3, 4}, {24, 23, 22, 21, 5}, {12, 13, 14, 15, 16}, {11, 17, 18, 19, 20}, {10, 9, 8, 7, 6}}));
        System.out.println(Arrays.deepToString(pool));
    }

    public static node T = null;
    public static int[][] pool = null;
    public static List<node> list = null;

    public static int swimInWater(int[][] grid) {
        list = new ArrayList<>();
        pool = new int[grid.length][grid.length];
        // 0 创建一个一打通的泳池
        // 1 创建一个一个单调的领域队列
        T = new node(0, 0, grid[0][0]); // 起始点的时间
//        pool[0][0] = 1;
        add(grid, 0, 0);
        // 2 将起始点的邻域添加到队列中
        while (!list.isEmpty()&&T.x<grid.length-1) {
            // 3 循环执行（终点不在已打通的泳池）
            node node = list.remove(0);
            //      3.1 获取队列顶部的点，并将其添加到已打通的泳池（跟新最大值）
            //      3.2 处理领域
            //          3.2.1 判断领域值大小；大（添加到邻域中），小（则添加到一打通的泳池，跟新最大值，重复处理邻域执行3.2）
            add(grid,node.x,node.y);
        }
        return T.v;
    }

    public static void add(int[][] grid, int x, int y) {
        if (pool[x][y] != 1) {  // 该点不在一已打通的泳池里
            // 添加该点
            pool[x][y] = 1;
            T.v = Math.max(T.v, grid[x][y]); // 保存已打通泳池需要最大时间
            if (x == y && x == grid.length - 1) {
                T.x = x;
                T.x = y;
                return;
            }
            // 处理邻域的点
            charge(x + 1, y, grid);
            charge(x - 1, y, grid);
            charge(x, y + 1, grid);
            charge(x, y - 1, grid);
        }
    }

    public static void charge(int x, int y, int[][] grid) {
        if (x >= 0 && x < grid.length && y >= 0 && y < grid.length && pool[x][y] != 1) {
            if (grid[x][y] > T.v) {  // 该点时间大于当前时间，将其加入领域
                int index = find(list, grid[x][y]);
                node n = new node(x, y, grid[x][y]);
                list.add(index, n);
            } else {  // 将其加入pool
                add(grid, x, y);
            }
        }
    }

    public static int find(List<node> list, int target) {
        int l = 0, r = list.size(), mid = 0;
        while (l < r) {
            mid = l + (r - l) / 2;
            if (list.get(mid).v <= target) {
                l = mid + 1;
            } else
                r = mid;
        }
        return l;
    }
}

class node {
    public int x;
    public int y;
    public int v;

    public node() {
    }

    public node(int x, int y, int v) {
        this.x = x;
        this.y = y;
        this.v = v;
    }
}